﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Recursives
{
    class FibTest
    {
        public static void Test()
        {
            for (int i = 0; i < 10; i++)
            {
                Console.WriteLine(RecursiveFib(i));
            }

            for (int i = 0; i < 10; i++)
            {
                Console.WriteLine(StackFib(i));
            }
        }

        private static long RecursiveFib(long n)
        {
            if (n == 0 || n == 1)
            {
                return n;
            }
            else
            {
                return RecursiveFib(n - 1) + RecursiveFib(n - 2);
            }
        }

        private enum CodeAddress
        {
            Start,
            AfterFirstRecursiveCall,
            AfterSecondRecursiveCall
        }

        private class StackFrame
        {
            public long N { get; set; }

            public CodeAddress CodeAddress { get; set; }

            public long FirstRecursiveCallResult { get; set; }

            public long SecondRecursiveCallResult { get; set; }
        }

        private static long StackFib(long n)
        {
            var stack = new Stack<StackFrame>();
            stack.Push(new StackFrame
            {
                N = n,
                CodeAddress = CodeAddress.Start
            });

            long result = 0;

            while (stack.Count > 0)
            {
                var current = stack.Peek();

                switch (current.CodeAddress)
                {
                    case CodeAddress.Start:
                        if (current.N == 0 || current.N == 1)
                        {
                            result = current.N;
                            stack.Pop();
                        }
                        else
                        {
                            current.CodeAddress = CodeAddress.AfterFirstRecursiveCall;
                            stack.Push(new StackFrame
                            {
                                N = current.N - 1,
                                CodeAddress = CodeAddress.Start
                            });
                        }
                        break;
                    case CodeAddress.AfterFirstRecursiveCall:
                        current.FirstRecursiveCallResult = result;

                        current.CodeAddress = CodeAddress.AfterSecondRecursiveCall;
                        stack.Push(new StackFrame
                        {
                            N = current.N - 2,
                            CodeAddress = CodeAddress.Start
                        });
                        break;
                    case CodeAddress.AfterSecondRecursiveCall:
                        current.SecondRecursiveCallResult = result;

                        result = current.FirstRecursiveCallResult + current.SecondRecursiveCallResult;
                        stack.Pop();
                        break;
                }
            }

            return result;
        }
    }
}
